#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""
https://www.geeksforgeeks.org/check-if-the-given-push-and-pop-sequences-of-stack-is-valid-or-not/
"""

INVALID = -1        # 既不是TOP, 又不在new中
TOP = 0
NEW = 1

def ele_status(online_stack, in_order, push_max_idx, ele):
    if online_stack and ele == online_stack[-1]:
        return TOP

    # 还没有压栈
    if ele in in_order[push_max_idx+1:]:
        return NEW

    # 只能出栈栈顶
    if ele in online_stack:
        print("not top, in online_stack")
        return INVALID

    # 在out_stack中, 已经出过栈.
    print("already out stack")
    return INVALID

def is_valid_pop_order(in_order, out_order):
    # [a, b, c, d, e], [b, c, d, e, a]
    # [a, b, c, d, e], [b, a, e, c, d]
    push_max_idx = -1

    online_stack = []       # 当前栈
    outed_eles = set()         # 已经出了的元素

    # for push_idx, out_ele in enumerate(out_order):
    for out_ele in out_order:
        # status = ele_status(online_stack, outed_eles, out_ele)
        status = ele_status(online_stack, in_order, push_max_idx, out_ele)
        if status == INVALID:
            return False

        outed_eles.add(out_ele)     # 一下都合理, 所以先加入outed_eles

        if status == TOP:
            online_stack.pop()
        elif status == NEW:
            # 因为此次push_idx指向的out_ele已经出栈了, 所以不加入online_stack
            # FIXME
            push_idx = in_order.index(out_ele)
            # online_stack += out_order[push_max_idx+1:push_idx]
            online_stack += in_order[push_max_idx+1:push_idx]
            push_max_idx = push_idx

        # print(status, online_stack, outed_eles)
        continue
        # print('cant status ', status)
        # assert False, "can't reach here"

    return True


def main():
    print("start main")
    valid = is_valid_pop_order("abcde", "abcde")
    print(valid)

    valid = is_valid_pop_order("abcde", "abced")
    print(valid)

    valid = is_valid_pop_order("abcde", "cab")
    print(valid)


    in_order = [5,  9,  1,  8 , 13 ,  4,  2,  7]
    out_order1 = [8, 4 , 13,  1,  7,  2, 9,  5]
    out_order2 = [8, 4 , 13,  1,  5,  4, 2,  7 , 9]
    valid = is_valid_pop_order(in_order, out_order1)
    print(valid)
    valid = is_valid_pop_order(in_order, out_order2)
    print(valid)

    valid = is_valid_pop_order("12345", "43512")
    print(valid)
    # pPush中序列为：[5   9   1   8    13     4   2    7]
    # 给出一个出栈序列pPop：[8   4    13   1   7   2  9   5]，这个出栈序列是正确的。
    # 给出另一个出栈序列pPop:[8   4    13   1   5   4   2     7    9]，这个出栈序列就是错误的，因为8第一个出栈，说明栈中已经压入过5  9  1三个元素，它们还存在栈中


if __name__ == "__main__":
    main()
